﻿/******************************************************************************
	Cobalt - utility libraries for building XNA games
	Copyright (C) 2008 Philip Djonov

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.
******************************************************************************/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Cobalt
{
	/// <summary>
	/// A simple unordered set.
	/// </summary>
	/// <typeparam name="T">The type of value the set contains.</typeparam>
	internal class Set<T> : ICollection<T>, ICloneable
	{
		public static readonly Set<T> Empty = new Set<T>();
		static Set()
		{
			Empty.Seal();
		}

		private struct Entry
		{
			public int HashCode;
			public T Value;
			public int Next; //either next in a conflict chain, or next in a free list
		}

		private int[] heads;
		private Entry[] entries;
		private IEqualityComparer<T> comparer;
		private int count, numFree, freeList;
		private bool isSealed;

		/// <summary>
		/// The <see cref="IEqualityComparer{T}"/> used to hash and compare set values.
		/// </summary>
		public IEqualityComparer<T> Comparer { get { return comparer; } }

		#region Setup
		/// <summary>
		/// Initializes a new <see cref="Set{T}"/> with minimal storage and
		/// the default <see cref="Comparer"/>.
		/// </summary>
		public Set()
			: this( 0, null )
		{
		}

		/// <summary>
		/// Initializes a new <see cref="Set{T}"/> with a given initial capacity
		/// and a provided <see cref="Comparer"/>.
		/// </summary>
		/// <param name="capacity">
		/// The initial capacity of the <c>Set</c>. If this value is zero, no
		/// storage will be allcoated until something is added to the <c>Set</c>.
		/// </param>
		/// <param name="comparer">
		/// The comparer to use when hashing and comparing set members. Passing
		/// <c>null</c> will default this to <typeparamref name="T"/>'s implementation
		/// of <see cref="Object.GetHashCode()"/> and <see cref="Object.Equals( Object )"/>.
		/// </param>
		public Set( int capacity, IEqualityComparer<T> comparer )
		{
			if( capacity < 0 )
				throw new ArgumentOutOfRangeException( "capacity" );

			this.comparer = comparer != null ? comparer : EqualityComparer<T>.Default;

			if( capacity > 0 )
				Allocate( capacity );
		}

		private void Allocate( int capacity )
		{
			if( capacity < 3 )
				//we hates the 2
				capacity = 3;

			capacity = Helpers.GetPrime( capacity );

			if( heads == null )
			{
				//allocate new
				heads = new int[capacity];
				entries = new Entry[capacity];
			}
			else
			{
				//rehash

				Enumerator e = new Enumerator( this );

				//e has its own copy of the arrays so we're cool to trash them
				heads = new int[capacity];
				entries = new Entry[capacity];
				count = 0;
				numFree = 0;

				while( e.MoveNext() )
				{
					Insert( e.Current, false );
				}
			}
		}
		#endregion

		#region ReadOnlyView
		/// <summary>
		/// A read-only view of a <see cref="Set{T}"/>.
		/// </summary>
		public sealed class ReadOnlyView : ICollection<T>
		{
			private Set<T> owner;
			internal ReadOnlyView( Set<T> owner )
			{
				this.owner = owner;
			}

			/// <summary>
			/// Gets whether a value is in the set.
			/// </summary>
			/// <param name="item">The item to check for.</param>
			/// <returns>True if the item is in the set, false otherwise.</returns>
			public bool this[T item]
			{
				get { return owner[item]; }
			}

			#region ICollection<T> Members

			void ICollection<T>.Add( T item )
			{
				throw new NotSupportedException();
			}

			void ICollection<T>.Clear()
			{
				throw new NotSupportedException();
			}

			/// <summary>
			/// Gets whether a value is in the set.
			/// </summary>
			/// <param name="item">The item to check for.</param>
			/// <returns>True if the item is in the set, false otherwise.</returns>
			public bool Contains( T item )
			{
				return owner.Contains( item );
			}

			/// <summary>
			/// Copies all members of the set to an array.
			/// </summary>
			/// <param name="array">The array to copy the values to.</param>
			/// <param name="arrayIndex">The index to begin copying at.</param>
			/// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
			/// <exception cref="ArgumentOutOfRangeException">
			/// <paramref name="arrayIndex"/> is negative, or it is past the end of the array,
			/// or there is not enough space in <paramref name="array"/> past <paramref name="arrayIndex"/>
			/// to store <see cref="Count"/> elements.
			/// </exception>
			public void CopyTo( T[] array, int arrayIndex )
			{
				owner.CopyTo( array, arrayIndex );
			}

			/// <summary>
			/// Gets the number of elements in the set.
			/// </summary>
			public int Count
			{
				get { return owner.Count; }
			}

			bool ICollection<T>.IsReadOnly
			{
				get { return true; }
			}

			bool ICollection<T>.Remove( T item )
			{
				throw new NotSupportedException();
			}

			#endregion

			/// <summary>
			/// Gets an enumerator over the elements in the set.
			/// </summary>
			/// <returns></returns>
			public Set<T>.Enumerator GetEnumerator()
			{
				return owner.GetEnumerator();
			}

			#region IEnumerable<T> Members

			IEnumerator<T> IEnumerable<T>.GetEnumerator()
			{
				return owner.GetEnumerator();
			}

			#endregion

			#region IEnumerable Members

			System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
			{
				return owner.GetEnumerator();
			}

			#endregion
		}

		/// <summary>
		/// Creates a new <see cref="ReadOnlyView"/> of this set.
		/// </summary>
		/// <returns>A new <see cref="ReadOnlyView"/> of this set.</returns>
		public ReadOnlyView CreateReadOnlyView()
		{
			return new ReadOnlyView( this );
		}
		#endregion

		/// <summary>
		/// Makes the <see cref="Set{T}"/> immutable.
		/// </summary>
		/// <remarks>
		/// There is no way to make a set mutable once <c>Seal</c>
		/// has been called. You must replace it with a <see cref="Clone"/>
		/// if you need to make changes.
		/// </remarks>
		public void Seal()
		{
			isSealed = true;
		}

		#region Main Add/Remove

		/// <summary>
		/// Gets or sets a value that indicates a value's presence in the <see cref="Set{T}"/>.
		/// </summary>
		/// <param name="item">
		/// The value to query, or include/exclude.
		/// </param>
		/// <exception cref="ArgumentNullException"><paramref name="item"/> is <c>null</c>.</exception>
		/// <exception cref="InvalidOperationException">
		/// The set has been sealed.
		/// </exception>
		/// <returns>
		/// True if the value is included in this <see cref="Set{T}"/>, false otherwise.
		/// </returns>
		public bool this[T item]
		{
			get { return Contains( item ); }
			set
			{
				if( isSealed )
					throw new InvalidOperationException( "This set has been sealed." );

				if( value )
					Add( item );
				else
					Remove( item );
			}
		}

		/// <summary>
		/// Adds an item to the set, if it is not already included.
		/// </summary>
		/// <param name="item">The item to add to the set.</param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="item"/> is <c>null</c>.
		/// </exception>
		/// <exception cref="InvalidOperationException">
		/// The set has been sealed.
		/// </exception>
		public void Add( T item )
		{
			Insert( item, false );
		}

		/// <summary>
		/// Adds an item to the set, throwing an exception if the item
		/// is already included.
		/// </summary>
		/// <param name="item">The item to add to the set.</param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="item"/> is <c>null</c>.
		/// </exception>
		/// <exception cref="ArgumentException">
		/// <paramref name="item"/> is already a member of this set.
		/// </exception>
		/// <exception cref="InvalidOperationException">
		/// The set has been sealed.
		/// </exception>
		public void AddUnique( T item )
		{
			Insert( item, true );
		}

		/// <summary>
		/// Removes an item from the set.
		/// </summary>
		/// <param name="item">The item to add to the set.</param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="item"/> is <c>null</c>.
		/// </exception>
		/// <exception cref="InvalidOperationException">
		/// The set has been sealed.
		/// </exception>
		/// <returns>
		/// True if the item was removed, false if it was not a member
		/// in the first place.
		/// </returns>
		public bool Remove( T item )
		{
			if( item == null )
				throw new ArgumentNullException( "value" );

			if( isSealed )
				throw new InvalidOperationException( "This set has been sealed." );

			if( heads == null )
				return false;

			int hash = comparer.GetHashCode( item );
			int headIdx = (hash & 0x7FFFFFFF) % heads.Length;

			if( heads[headIdx] == 0 )
				return false;

			for( int prior = -1, entryIdx = heads[headIdx];
				entryIdx >= 0;
				prior = entryIdx, entryIdx = entries[entryIdx].Next )
			{
				if( entries[entryIdx].HashCode == hash &&
					comparer.Equals( entries[entryIdx].Value, item ) )
				{
					//found it

					if( prior == -1 )
					{
						//prior is the head
						heads[headIdx] = entries[entryIdx].Next != -1 ? entries[entryIdx].Next : 0;
					}
					else
					{
						//prior is an entry
						entries[prior].Next = entries[entryIdx].Next;
					}

					entries[entryIdx].Value = default( T ); //make sure we're not holding dead references
					FreeEntry( entryIdx );

					return true;
				}
			}

			return false;
		}

		private void Insert( T value, bool throwOnDup )
		{
			if( value == null )
				throw new ArgumentNullException( "value" );

			if( isSealed )
				throw new InvalidOperationException( "This set has been sealed." );

			if( heads == null )
				Allocate( 0 );

			int hash = comparer.GetHashCode( value );

		resized:
			int headIdx = (hash & 0x7FFFFFFF) % heads.Length;

			if( heads[headIdx] == 0 )
			{
				//no collision
				int newEntryIdx = AllocEntry();
				if( newEntryIdx < 0 )
					goto resized;

				entries[newEntryIdx].HashCode = hash;
				entries[newEntryIdx].Value = value;
				entries[newEntryIdx].Next = -1;

				heads[headIdx] = ~newEntryIdx;
			}
			else
			{
				//collision

				//check to see if it is already in the set
				for( int entryIdx = ~heads[headIdx]; entryIdx >= 0; entryIdx = entries[entryIdx].Next )
				{
					if( entries[entryIdx].HashCode == hash &&
						comparer.Equals( entries[entryIdx].Value, value ) )
					{
						//already in the set
						if( throwOnDup )
							throw new ArgumentException( "The value is already in this set." );

						//nothing more to do
						return;
					}
				}

				//it is not
				int newEntryIdx = AllocEntry();
				if( newEntryIdx < 0 )
					goto resized;

				entries[newEntryIdx].HashCode = hash;
				entries[newEntryIdx].Value = value;
				entries[newEntryIdx].Next = ~heads[headIdx];

				heads[headIdx] = ~newEntryIdx;
			}
		}

		#region AllocEntry/FreeEntry
		private int AllocEntry()
		{
			if( numFree != 0 )
			{
				int ret = freeList;

				freeList = entries[freeList].Next;
				numFree--;
				count++;

				return ret;
			}
			else if( count < entries.Length )
			{
				int ret = count;

				count++;

				return ret;
			}
			else //must grow
			{
				Allocate( entries.Length * 2 );
				return -1; //signal Add to restart
			}
		}

		private void FreeEntry( int entryIdx )
		{
			if( entryIdx < count - 1 )
			{
				//if it's not the end one, toss it into the free list
				entries[entryIdx].Next = freeList;
				freeList = entryIdx;
				numFree++;
			}

			count--;
		}
		#endregion

		#endregion

		#region ICollection<T> Members

		/// <summary>
		/// Removes all items from the set.
		/// </summary>
		/// <exception cref="InvalidOperationException">The set has been sealed.</exception>
		public void Clear()
		{
			if( isSealed )
				throw new InvalidOperationException( "This set has been sealed." );

			Array.Clear( heads, 0, heads.Length );
			Array.Clear( entries, 0, entries.Length );

			count = 0;
			numFree = 0;
		}

		/// <summary>
		/// Queries whether a value is included in the set.
		/// </summary>
		/// <param name="item">
		/// The value to query.
		/// </param>
		/// <returns>
		/// True if <paramref name="item"/> is in the set, false otherwise.
		/// </returns>
		public bool Contains( T item )
		{
			if( item == null )
				return false;

			if( heads == null )
				return false;

			int hash = comparer.GetHashCode( item );
			int headIdx = (hash & 0x7FFFFFFF) % heads.Length;

			if( heads[headIdx] == 0 )
				return false;

			for( int entryIdx = heads[headIdx]; entryIdx >= 0; entryIdx = entries[entryIdx].Next )
			{
				if( entries[entryIdx].HashCode == hash &&
					comparer.Equals( entries[entryIdx].Value, item ) )
				{
					//found it
					return true;
				}
			}

			return false;
		}

		/// <summary>
		/// Copies all members of the set to an array.
		/// </summary>
		/// <param name="array">The array to copy the values to.</param>
		/// <param name="arrayIndex">The index to begin copying at.</param>
		/// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="arrayIndex"/> is negative, or it is past the end of the array,
		/// or there is not enough space in <paramref name="array"/> past <paramref name="arrayIndex"/>
		/// to store <see cref="Count"/> elements.
		/// </exception>
		public void CopyTo( T[] array, int arrayIndex )
		{
			if( array == null )
				throw new ArgumentNullException( "array" );
			if( arrayIndex < 0 || arrayIndex > array.Length )
				throw new ArgumentOutOfRangeException( "arrayIndex" );
			if( array.Length - arrayIndex < count )
				throw new ArgumentOutOfRangeException( "arrayIndex" );

			int i = arrayIndex;
			foreach( T val in this )
				array[i++] = val;
		}

		/// <summary>
		/// Gets the number of elements in the set.
		/// </summary>
		public int Count
		{
			get { return count; }
		}

		/// <summary>
		/// Gets whether the <see cref="Set{T}"/> has been <see cref="Seal"/>ed or not.
		/// </summary>
		public bool IsReadOnly
		{
			get { return !isSealed; }
		}

		#endregion

		#region ICloneable Members

		/// <summary>
		/// Creates a copy of the set.
		/// </summary>
		/// <returns>
		/// A copy of this set.
		/// </returns>
		public Set<T> Clone()
		{
			Set<T> ret = new Set<T>( 0, comparer );

			if( heads != null )
			{
				ret.heads = new int[heads.Length];
				Array.Copy( heads, ret.heads, heads.Length );

				ret.entries = new Entry[entries.Length];
				Array.Copy( entries, ret.entries, entries.Length );

				ret.count = count;
				ret.freeList = freeList;
				ret.numFree = numFree;
			}

			return ret;
		}

		object ICloneable.Clone()
		{
			return Clone();
		}

		#endregion

		#region Enumerable
		/// <summary>
		/// An enumerator for a <see cref="Set{T}"/>.
		/// </summary>
		public struct Enumerator : IEnumerator<T>
		{
			private int headIndex, chainIndex;
			private int[] heads;
			private Entry[] entries;

			internal Enumerator( Set<T> set )
			{
				this.heads = set.heads;
				this.entries = set.entries;

				this.headIndex = -1;
				this.chainIndex = -1;
			}

			#region IEnumerator<T> Members

			/// <summary>
			/// The currently enumerated value.
			/// </summary>
			public T Current
			{
				get
				{
					if( chainIndex < 0 )
						throw new InvalidOperationException();

					return entries[chainIndex].Value;
				}
			}

			#endregion

			#region IDisposable Members

			void IDisposable.Dispose()
			{
			}

			#endregion

			#region IEnumerator Members

			object System.Collections.IEnumerator.Current
			{
				get { return Current; }
			}

			/// <summary>
			/// Moves to the next element in the set.
			/// </summary>
			/// <returns>
			/// True if there is another element, false otherwise.
			/// </returns>
			public bool MoveNext()
			{
				for( ; ; )
				{
					if( chainIndex < 0 )
					{
						//ran out of chain, find the next head
						for( headIndex++; headIndex < heads.Length; headIndex++ )
						{
							if( heads[headIndex] != 0 )
								//victory!
								break;
						}

						if( headIndex == heads.Length )
							//out of entries
							return false;

						chainIndex = ~heads[headIndex];
						return true;
					}

					chainIndex = entries[chainIndex].Next;
					if( chainIndex >= 0 )
						return true;
				}
			}

			/// <summary>
			/// Moves to one position before the first element.
			/// </summary>
			public void Reset()
			{
				this.headIndex = -1;
				this.chainIndex = -1;
			}

			#endregion
		}

		/// <summary>
		/// Gets an enumerator over the set.
		/// </summary>
		/// <returns>
		/// An enumerator over the set.
		/// </returns>
		public Enumerator GetEnumerator()
		{
			return new Enumerator( this );
		}

		#region IEnumerable<T> Members

		IEnumerator<T> IEnumerable<T>.GetEnumerator()
		{
			return GetEnumerator();
		}

		#endregion

		#region IEnumerable Members

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		#endregion
		#endregion
	}
}
